package org.nowcoder.leetcode.linkedList;


import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;

/**
 * Title  : 146. LRU Cache
 * Source : https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-interview-150
 * Author : XrazYang
 * Date   : 2023-08-10
 *
 * Note: 继承LinkedHashMap，重写removeEldestEntry，LinkedHashMap可以指定访问模式：- true for access-order, false for insertion-order
 */
public class LeetCode_146 {
    class LRUCache {
        private final int capacity;
        private int size;
        private final Map<Integer, Integer> cache;
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            cache = new HashMap<>();
        }

        public int get(int key) {
            Integer value = cache.getOrDefault(key, -1);
            if (value != -1) {
                deque.remove(key);
                deque.offer(key);
            }
            return value;
        }

        public void put(int key, int value) {
            Integer val = cache.getOrDefault(key, -1);
            if (val == -1) { //不存在
                if (this.size >= capacity) { //超过容量
                    Integer old = deque.poll();
                    cache.remove(old);
                    this.size--;
                }
                cache.put(key, value);
                deque.offer(key);
                this.size++;
            } else { //存在，更新值即可
                deque.remove(key);
                cache.put(key, value);
                deque.offer(key);
            }
        }
    }
}
